- I have a question for you.
What's the longest time a computer program
can run before it stops?
A year, a decade, a century,
a millennia, or even the age of the universe?
If you don't know the answer, you are not alone.
This question has baffled
and mesmerized mathematicians for over 60 years.
Why?
It has surprising connections
to some of math's oldest and most famous unsolved problems.
It offers a window into where the fundamental logic
of math starts to crumble
and could even reveal the edge of what's humanly knowable.
And just last year after 30 years of no progress,
a major breakthrough was made.
But what makes this discovery truly remarkable
isn't just the result,
it's the weird way that it happened.
It wasn't solved the way most maths problems are solved
by a team of highly skilled researchers at a university.
It was solved by an unlikely group of math enthusiasts,
mostly without formal academic education,
who all met online through a website
announcing something called The Busy Beaver Challenge.
By the end of this video,
you'll know exactly what that means,
as well as the surprising story behind this breakthrough
and exactly what it was they discovered.
It all started with one mathematician
and a game he invented.
(keyboard tapping) (gentle upbeat music)
When most people were asking,
"What problems can a computer solve?"
a mathematician named Tibor Rado asked,
"What problems can't a computer solve?"
How far could an algorithm,
a step-by-step mindless set of instructions really get us?
Were all problems computable?
Or were some too complicated for a computer to handle?
What are the limits of computation?
At the time, the idea of what a computer
could solve was well understood
thanks to Alan Turing.
He thought up these simple theoretical devices
called Turing machines that capture
exactly what it means to compute something.
Turing theorized that these simple
kind of computers could perform any possible computation.
They're the blueprint
upon which all our modern digital computers are based,
even the computer you're watching this video on.
Rado did end up finding a problem
that a computer can't solve.
And to understand it, we need to know
how Turing machines work.
A Turing machine is made up
of an infinitely long tape divided up into cells.
A symbol like a zero or a one is in each cell.
A head reads the symbol,
and depending on what it is, can erase it,
write a new symbol, move to the left,
or move to the right.
Every Turing machine has a unique set of rules
which tells it what to do.
For example, rule one might say, "If you read a zero,
write a one in the current cell,
move one cell to the right and go to rule two."
There's also a special rule which tells the machine
when to stop running.
A Turing machine can have any fixed number of rules.
Some have three rules, some have 10 rules.
Some have 100 rules.
Usually the more rules a Turing machine has,
the more complicated computations it can do.
If you want to know more about how Turing machines work,
I've made a whole video about them,
which I've linked in the description.
But here's the important bit you need to know.
Starting from rule one,
a Turing machine will either eventually halt
or it will run forever.
So Turing machines come in two types,
halting and non-halting.
Rado sorted Turing machines into groups
according to how many rules they have.
He grouped all the one rule machines together,
all the two rule machines together,
all the three rule machines together and so on.
In each group, some machines will meander along forever,
some will halt pretty quickly,
and some will take much longer to halt.
One will be the last to halt.
This was the machine Rado was interested in,
the longest running of all the halting machines.
Rado named them busy beavers
because of how they forage along the tape.
The number of steps the busy beaver takes
before halting is called its busy beaver number,
or BBN for short.
For example, for a one rule Turing machine,
if you want to make sure it halts,
you can really only have the rule
that no matter what it reads, it halts.
So the busy beaver number
of a one rule Turing machine is just one,
as it only takes one step before halting.
Getting BB 2 is a bit more complicated
as there are 6,561 two rule machines.
But it's been shown that busy beaver number two
runs for six steps before it halts.
Now, here's the cool part.
Rado found that finding busy beavers
and their busy beaver numbers is uncomputable.
There's no general algorithm
or formula a computer can perform to find them.
The only way to find a busy beaver
is to manually examine each machine one by one
and see how long they run.
He'd found what he was looking for.
Rado turned his search for busy beavers into a game.
To play, you have to do two things,
discard all the non-halting machines
and search the remaining machines
for the one that runs the longest.
Little did he know that this game would have roots
in some of math's biggest open problems
and turn into a decades long hunt
that would haunt generations of mathematicians.
But what do busy beavers have to do
with these famous problems?
To understand, let's take a look at one of them.
(keyboard tapping) (gentle upbeat music)
The Goldbach conjecture says
that every even integer greater than two
is the sum of two primes.
For example, four is the sum of two and two, a prime.
28 is the sum of 17 and 11, both primes.
Do this for any even number and it'll work.
This seemingly simple conjecture
has defied proof for almost 300 years.
Yet so far we know that it's true
for all even numbers
up to four times 10 to the power of 18.
But checking individual cases
isn't good enough for mathematicians.
They need hard, logical proof
that it's true for all even integers.
This is where a busy beaver might come in handy.
Suppose you wrote a computer program
that checks every even integer starting from four,
one by one, and halts only if it finds a number
that cannot be written as the sum of two primes.
Such a program has been shown to be computable
by a Turing machine with 27 rules.
But here's the cool part.
If we knew the value of BB 27,
we could solve the Goldbach conjecture.
If our program does halt,
then it must halt in BB 27 steps or less.
If it halts within this number,
the program has found an even integer
that can't be written as the sum of two primes.
This would prove Goldbach's conjecture wrong.
But if the machine continues running past BB 27 steps,
then we'd know it will never halt,
as all the halting machines halt before BB 27 steps.
Goldbach's conjecture would be proven true.
So the solution to the Goldbach conjecture
can be reduced to finding the 27 rule busy beaver.
There are other similar Turing machines
for other unsolved problems in math,
like the Riemann hypothesis.
In fact, any mathematical statement
that can be written in a computer language
can be proven in this way.
It's amazing to think
that doing something in a finite number
of steps can tell us something about
an infinite amount of numbers.
So what are we waiting for?
Why don't we figure out BB 27
and then solve the Goldbach conjecture,
and all other unsolved problems in math for that matter?
(keyboard tapping) (gentle upbeat music)
We've seen the one and two rural busy beavers.
But the three rule, well,
there are over five million three rule Turing machines,
and over seven billion four rule machines.
Remember that the only way to find a busy beaver
is by examining each machine individually.
It's like finding a needle in a giant digital haystack,
where the haystacks increase
more than exponentially in size
as the number of rules gets bigger.
But surely we could make our lives easier
by getting rid of all the non-halting machines
and then just looking through what's left.
The non-halting machines
are definitely not the busy beaver,
as by definition, the busy beaver halts.
But Turing has a nasty surprise for us.
He proved that there is no reliable, repeatable way
to tell if a Turing machine will ever halt.
If a machine has run for 100 years,
it may halt in 100 years and one day,
and there's no way that we can tell
except to just wait and find out.
This result is called the halting problem,
and I've made a video all about it,
which I've linked in the description.
It's actually a really cool result, even if it is a pain.
So it turns out that both steps
of Rado's game are extremely difficult.
One, because of the halting problem, and two,
because there are so many machines to search through.
But have we at least found the third busy beaver?
(keyboard tapping) (gentle upbeat music)
In the mid 1960s, a persistent math grad student
at Oregon State University,
whose mascot is coincidentally Benny the Beaver,
gave it a go.
His name was Allen Brady,
and he realized that he could sort through
all 5 million of the three state Turing machines
if he ignored large chunks of them,
such as those that halted immediately.
He also recognized that many non-halting machines
were easy to spot because they began looping,
performing the same instructions over and over.
Brady coded up this technique
of discarding the obvious non-busy beavers
into a computer program.
He just needed a computer powerful enough to run it.
In 1964, that wasn't easy.
Brady had to drive 90 miles to a town called Beaverton,
I'm not joking,
to access a state-of-the-art computer
at the Oregon Regional Primate Center.
But oh no, he was too late.
Rado and his grad student
Shen Lin had beaten him to the punch.
They'd found the third busy beaver,
it halted in 21 steps.
But Brady didn't lose hope.
He immediately moved on to finding the fourth busy beaver.
But there was a problem.
Four rule Turing machines
can do much more complicated computations
than three rule ones.
This means it was much harder
to spot the non-halting machines
because many of them don't get stuck in infinite loops,
which Brady's program was good at recognizing.
But nevertheless, two years later,
he'd found a four rule Turing machine
that halted in 107 steps.
It would take him several more years of painstaking work
to prove that this machine
was indeed the fourth busy beaver.
It was the last busy beaver
humanity would know for over 40 years.
Which brings us to April, 2024,
The Busy Beaver Challenge
and a maverick group of math enthusiasts.
Despite there being nearly 17 trillion
5 rule Turing machines,
they managed to do what no one else could,
they found the fifth busy beaver and BB 5.
To put into perspective
what a phenomenal feat this is,
if you just listed 17 trillion machines
at a rate of one per millisecond,
it would take over 500 years to list them all.
So how did they pull it off?
(keyboard tapping) (gentle upbeat music)
Okay, we actually need to jump back for a sec.
Around 20 years after Brady
found the fourth busy beaver,
the University of Dortmund held a competition
to find the fifth busy beaver.
Over 100 contenders showed up,
but by the end of the competition,
no one had conclusively found BB 5.
However, one contestant had found a machine
that halted in 100,000 steps.
The contest was reported in "Scientific American,"
which popularized the game to a new generation
of mathematicians, and this number soon blew up
to over 2 million steps,
pushing the potential BB 5 up even higher.
But everybody was shocked
when grad students Heiner Marxen
and Jurgen Buntrock discovered a five state machine
that halted in 47,176,870 steps.
Was this the fifth busy beaver?
They had no idea that it would take over 30 years
to answer this question.
Progress was slow going for decades,
but things really took off in 2021.
A grad student named Tristan Sterin
tried out Brady's original method with a twist.
Like Brady, Sterin wrote a code that weeded out machines
that obviously weren't the fifth busy beaver.
He collected all the remaining machines
and dumped them into a database for examination.
By December, 2021, the database was complete
and held over 88 million machines.
88 million possible busy beavers.
If he could show that each of these machines
either halted before 47 million steps
or never halted, then he would know
that this 47 million step machine
really was busy beaver number five.
But how was he going to sift through this mountain
of 88 million machines?
Sterin knew he needed help,
so he founded The Busy Beaver Challenge,
an online community anyone could join.
Over time, the community grew
to more than 20 contributors from all around the world,
most of them without traditional academic credentials.
Together, they began chipping away
at the 88 million machines,
keeping the others updated
on their progress through Discord.
But there was a big problem,
some machines were nearly impossible to classify.
One in particular developed
an especially scary reputation.
They called it Skelet number one.
What was tricky about it was that
it would sometimes act completely predictable
and sometimes completely wild.
There was really no telling what it would do next.
But after months of bashing their heads against a wall,
two contributors finally managed to crack it.
One of them was born in the town of Beaverton,
so maybe it was fate.
Shawn Ligocki and Pavel Kropitz showed
that Skelet number one did finally settle
into an infinitely repeating loop.
But after more than a trillion, trillion steps,
the loop was especially hard to find
because most infinite loops repeat within 1000 steps,
whereas Skelet number one's loop
was more than 8 billion steps long.
At long last, they'd managed to classify it
as a non-halting machine
and remove it from the list of potential busy beavers.
But there was a doubt growing in everyone's mind.
Could they trust the code they wrote?
Even if they did find the BB 5,
any small error in the code
of the program would make their result worthless.
They needed to prove that their code was free of errors.
But how can you prove that thousands of lines
of code have no errors?
This is where a new
and unlikely player joined in
with a secret weapon, a proof checker.
Proof checkers are programs
that don't run if they come across a logical error,
so mistakes are virtually impossible.
A good proof checker program could confirm
beyond a doubt that the team's proof
was free of faulty logic.
An ambitious university dropout
and self-taught programmer Mei stepped in.
Mei translated Skelet number one's proof
into a proof checking language called COQ,
verifying Ligocki's and Kropitz's result
that Skelet number one never halts.
Little by little, the mountain began to dwindle,
with proofs of non-busy beavers
trickling in from other participants.
But many proofs still hadn't been translated into COQ
to make sure they were legit and error free.
Then on May 10th, 2024,
a mysterious participant named MXDYS
made an announcement.
The COQ proof of BB 5 is finished.
They compiled the group's work
into a single 40,000 line COQ proof.
It was the final step in the busy beaver five mission.
An unlikely team of individuals from all over the world
who had come together over their love of math
had finally proven that this 47 million step
Turing machine was the fifth busy beaver.
It was a momentous feat,
but sadly, not everyone got to celebrate.
Allen Brady, the finder of the fourth busy beaver,
died just a few weeks before the proof was finished.
He was 90 years old.
Though he didn't live to see this milestone,
his legacy will always be intertwined
with the story of the busy beaver.
So what's next for the busy beaver saga?
(keyboard tapping) (gentle upbeat music)
Some of the team are already busy hunting
for the sixth busy beaver, but it isn't looking good.
They've shown that BB 6 is at least 10 to the power of 10,
to the power of 10, to the power of 10, to the power of 10,
to the power of 10 steps.
We wouldn't even be able to run a machine for this long
before the predicted heat death of the universe.
So it's quite possible
that BB 5 is the last busy beaver number we'll ever know.
But some of The Busy Beaver Challenge team
have moved on from busy beavers.
Mei has become obsessed
with the European International Rail Network
and is aspiring to be a train driver.
Will humanity ever find BB 6?
There are nearly 60 quadrillion six rule Turing machines.
With numbers this big,
the odds are stacked against us.
But if there's one thing this story has shown,
it's that when people want
to get to the bottom of something,
they'll find a way no matter how impossible it may seem.
The drive to understand, solve
and explore the unknown is what makes us human.
It makes me wonder, what made us like this?
Where did this insatiable curiosity come from?
What were the moments in our evolution
that made us the smartest species on earth?
The answer to these questions are actually fascinating,
and my friends over at Real Science
have made an entire series that explores
these questions plus many more,
like the origins of language,
and the breakthroughs that made us uniquely human.
It's called "Becoming Human,"
and I highly recommend it.
It's one of my favorite things on Nebula right now,
a platform that's quickly becoming the go-to space
for the best educational content on the internet.
Nebula is built and run by creators,
with the mission to be the best place
for us to make work that we couldn't make anywhere else.
I've always wanted to take my videos to the next level,
and Nebula is enabling that for our entire list of creators.
Better stories, better production value.
Taking creators to the next level
is what Nebula is all about.
And there are countless examples of what we're capable of,
and it's only getting better as time goes on.
It's completely ad free,
and most creators post
their YouTube videos there a week early.
To check out "Becoming Human,"
as well as hundreds of other top-notch,
thoughtful videos, completely ad free,
sign up with my link to get 40% off.
That's just $3 a month,
or $36 for the entire year.
Seriously, for the price of a latte,
you're getting access to some of the most interesting
and creative content out there.
Go to nebula.tv/upandatom
or click the link in the description.
You'll be supporting this channel,
as well as the entire educational community.
Thanks, and I'll see you next time.
Bye.
(upbeat music)